#include <iostream>
#include <stack>

/**
 * @brief 本程序使用c++11编写请注意使用c++11开关
 */

using namespace std;

enum OrderEnum {
    PreOrder = 0,
    InOrder = 1,
    PostOrder = 2,
};

class BST
{

    struct node
    {
        int data;
        node *left;
        node *right;
    };

    node *root;

    node *makeEmpty(node *t)
    {
        if (t == nullptr) 
            return nullptr;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return nullptr;
    }

    node *insert(int x, node *t)
    {
        if (t == nullptr)
        {
            t = new node;
            t->data = x;
            t->left = t->right = nullptr;
        }
        else if (x < t->data) {
            t->left = insert(x, t->left);
        }
        else if (x > t->data) {
            t->right = insert(x, t->right);
        }
        return t;
    }

    node *findMin(node *t)
    {
        if (t == nullptr) {
            return nullptr;
        }
        else if (t->left == nullptr) {
            return t;
        }
        else {
            return findMin(t->left);
        }
    }

    node *findMax(node *t)
    {
        if (t == nullptr) {
            return nullptr;
        }
        else if (t->right == nullptr) {
            return t;
        }
        else {
            return findMax(t->right);
        }
    }

    node *remove(int x, node *t)
    {
        node *temp;
        if (t == nullptr)
            return nullptr;
        else if (x < t->data)
            t->left = remove(x, t->left);
        else if (x > t->data)
            t->right = remove(x, t->right);
        else if (t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }
        else
        {
            temp = t;
            if (t->left == nullptr)
                t = t->right;
            else if (t->right == nullptr)
                t = t->left;
            delete temp;
        }

        return t;
    }

    void treewalk(node *t, OrderEnum type)
    {
        switch (type)
        {
            default:
            case InOrder:
                inOrder(t);
                break;
            case PreOrder:
                preOrder(t);
                break;
            case PostOrder:
                postOrder(t);
                break;
        }
    }

    void inOrder(node *t)
    {
        cout << "inOrder" << endl;
        stack<node *> s;
        node *curr = root;

        while (curr != nullptr || s.empty() == false)
        {
            while (curr != nullptr)
            {
                s.push(curr);
                curr = curr->left;
            }

            curr = s.top();
            s.pop();

            cout << curr->data << " ";
            curr = curr->right;
        }
    }

    void preOrder(node *root)
    {
        cout << "preOrder" << endl;
        // Base Case
        if (root == NULL)
            return;

        stack<node *> nodeStack;
        nodeStack.push(root);

        while (nodeStack.empty() == false)
        {
            struct node *node = nodeStack.top();
            cout << node->data << " ";
            nodeStack.pop();

            if (node->right)
                nodeStack.push(node->right);
            if (node->left)
                nodeStack.push(node->left);
        }
    }

    void postOrder(node *root)
    {
        cout << "postOrder" << endl;
        if (root == NULL)
            return;

        stack<node *> s1, s2;

        s1.push(root);
        node *node;

        while (!s1.empty())
        {
            node = s1.top();
            s1.pop();
            s2.push(node);

            if (node->left) {
                s1.push(node->left);
            }
            if (node->right) {
                s1.push(node->right);
            }
        }

        while (!s2.empty())
        {
            node = s2.top();
            s2.pop();
            cout << node->data << " ";
        }
    }

    node *find(node *t, int x)
    {
        if (t == nullptr) {
            return nullptr;
        }
        else if (x < t->data) {
            return find(t->left, x);
        }
        else if (x > t->data) {
            return find(t->right, x);
        }
        else {
            return t;
        }
    }

public:
    BST()
    {
        root = nullptr;
    }

    ~BST()
    {
        root = makeEmpty(root);
    }

    void insert(int x)
    {
        root = insert(x, root);
    }

    void remove(int x)
    {
        root = remove(x, root);
    }

    void display(OrderEnum type = InOrder)
    {
        treewalk(root, type);
        cout << endl;
    }

    void search(int x)
    {
        root = find(root, x);
    }
};

int main()
{
    BST t;
    t.insert(20);
    t.insert(25);
    t.insert(15);
    t.insert(10);
    t.insert(30);
    t.display();
    t.display(PreOrder);
    t.display(PostOrder);
    t.remove(20);
    // t.display();
    t.remove(25);
    // t.display();
    t.remove(30);
    return 0;
}